#!/usr/bin/env python
#encoding latin1

class heap:
	def __init__(self,comparar):
		self.count = 0
		self.vector = list()
		# comparar es una funcion que recibe dos datos
		# y devuelve < 0 si el primero es menor al segundo
		# 0 si son iguales
		# > 0 si el primero es mayor al segundo
		self.comparar = comparar
	def encolar(self,dato):
		self.vector.append(dato)
		self.upheap(self.count,dato)
		self.count += 1
	def ver_tope(self):
		return self.vector[0]
	def desencolar(self):
		if not self.count > 0:
			return None
		dato = self.ver_tope()
		self.count -= 1
		if self.count > 0:
			self.vector[0] = self.vector.pop()
			self.downheap(0,self.vector[0])
		return dato
	def upheap(self,where,dato):
		if where is 0:
			self.vector[where] = dato
			return
		# division entera
		padre = int((where - (2 - (where % 2))) / 2)
		dato_padre = self.vector[padre]
		if self.comparar(dato,dato_padre) > 0:
			self.vector[where] = dato_padre
			self.upheap(padre,dato)
		else:
			self.vector[where] = dato
	def downheap(self,where,dato):
		if where >= self.count:
			return
		hijo_izq = (where * 2) + 1
		hijo_der = hijo_izq + 1
		if hijo_izq >= self.count:
			self.vector[where] = dato
			return
		dato_hijo_izq = self.vector[hijo_izq]
		if hijo_der >= self.count:
			if self.comparar(dato,dato_hijo_izq) < 0:
				self.vector[where] = dato_hijo_izq
				# No es posible seguir
				self.vector[hijo_izq] = dato
			else:
				self.vector[where] = dato
			return
		dato_hijo_der = self.vector[hijo_der]
		if self.comparar(dato_hijo_izq, dato_hijo_der) > 0:
			pos = hijo_izq
			dato_hijo = dato_hijo_izq
		else:
			pos = hijo_der
			dato_hijo = dato_hijo_der
		if self.comparar(dato, dato_hijo) < 0:
			self.vector[where] = dato_hijo
			self.downheap(pos,dato)
		else:
			self.vector[where] = dato
